#include <stdio.h>

int a(int n){
	if( n==1 )  return 1;
	if( n==2 )  return 2;
	return a(n-1)*2+a(n-2);
}

int main(){
	int i,k,n;
	scanf("%d",&k);
	for( i=0; i<k; i++ ){
		scanf("%d",&n);
		printf("%d\n",a(n)%32767);
	}
	return 0;
}
